Parallel processing systems of the prior art have generally fallen into one of three classes, the first being Single Instruction Multiple Data (SIMD), which can perform the same operation over each element of a data set in parallel, such as vector processors. This type of parallel processing system is appropriate only for limited and specific types of applications and requires specialized programming to utilize.
The second type of system is the Distributed-Memory Multiple Instruction Multiple Data ("MIMD"). These multicomputers have general purpose processors but do not share memory and communicate with each other through some alternative medium. This type of system is easy to construct and may include many processors and be programmed in existing languages, but it is difficult to operate because of a need for explicit and slow communication between processors, making programming difficult.
The third type of parallel processing system, Shared-Memory MIMD, can be programmed with existing languages, but it is more difficult to build because of related costs and is limited to a small number of processors. Its advantage is that it provides a closer model of computation to existing serial systems, making it easier to utilize.
Traditional parallelism used to solve a problem may be characterized by three common elements; identifying the problem to be solved, partitioning the problem into smaller pieces that can be performed in parallel, and combining the results of these pieces. Existing systems are required to spend time determining what activities to perform in parallel, insuring those activities have adequate resources, and then combining obtained results.
Previously, two alternatives were available to address these determinations. One approach required the programmer to specify all of the activities and is the method adopted in the fork-join construct. Alternatively, in some systems these activities are performed entirely by compilers, as when FORTRAN do-loops are automatically partitioned for parallel execution.
The second approach disclosed by Robert H. Halstead, Jr. of Massachusetts Institute of Technology, in his article in the October, 1985 issue of ACM Transactions On Programming Languages And System, entitled: Multilisp: A Language for Concurrent Symbolic Computation provides the more powerful and general construct of a "future". When a computation is created, it is represented by (referenced through) a future object. Until its computation has been completed, the future object is undetermined. When the computation is complete, the future object becomes the value returned by the computation. The future object, once determined, is indistinguishable from this value. The advantage of futures over forks is that futures eliminate the need for an explicit joint operation.
Future objects are affected by two types of operations. A strict operation forces the future computation of the object and will wait until the value becomes available before continuing with the computation. Strict operations involve looking at the actual data type or value of an object. Non-strict operations only reference a pointer to the object, therefore, any operations not requiring the specific value represented by the future are not required to wait for the actual value of the future before completing the computation.
Future objects, as they exist in prior art, are built on top of the LISP programming language and therefore require considerable overhead. Also, to operate presently, all computations must first be scanned for futures, which again requires much overhead. In addition, original systems that incorporated future constructs required in excess of sixty thousand (60,000) bytes to represent a future, whereas the present invention only requires eight (8) bytes. These factors contribute to the inefficiency of the prior system in terms of limiting parallel speedup.
To effectively use parallelism, the associated overhead must not be prohibitive. Overhead is viewed as a cost to the computer and defined as the time required for the mechanisms to break the application into individual tasks and to initiate the parallel execution of those tasks. Therefore, the minimization of overhead is paramount to successful use of the system.
Presently, parallel systems contain two levels of parallelism known as the light-weight process and the heavy-weight process. These two levels are in fact two operating system levels which have different rates of overhead and properties.